interface TreeNode {
  [key: string]: unknown
  children?: TreeNode[]
}

/**
 * 将扁平数组转换为树形结构
 * @param items 扁平数组
 * @param idKey 自定义ID字段名，默认为'id'
 * @param parentIdKey 自定义父ID字段名，默认为'parentId'
 * @param childrenKey 自定义子节点字段名，默认为'children'
 * @returns 树形结构数组
 */
export function translateDataToTree<T extends TreeNode>(
  items: T[],
  idKey: string = 'id',
  parentIdKey: string = 'parentId',
  childrenKey: string = 'children',
): T[] {
  // 创建ID到节点的映射
  const itemMap: Record<string | number, T> = {}

  // 初始化所有节点
  items.forEach((item) => {
    itemMap[item[idKey] as string | number] = { ...item, [childrenKey]: [] }
  })

  const tree: T[] = []

  items.forEach((item) => {
    const node = itemMap[item[idKey] as string | number]
    const parentId = item[parentIdKey] as string | number | null | undefined

    if (parentId !== null && parentId !== undefined && itemMap[parentId]) {
      // 如果有父节点，则添加到父节点的children中
      ;(itemMap[parentId][childrenKey] as T[]).push(node)
    } else {
      // 否则作为根节点
      tree.push(node)
    }
  })

  return tree
}

/**
 * 将树形结构转换为扁平数组
 * @param tree 树形结构数组
 * @param idKey 自定义ID字段名，默认为'id'
 * @param parentIdKey 自定义父ID字段名，默认为'parentId'
 * @param childrenKey 自定义子节点字段名，默认为'children'
 * @returns 扁平数组
 */
export function treeToTranslateData<T extends TreeNode>(
  tree: T[],
  idKey: string = 'id',
  parentIdKey: string = 'parentId',
  childrenKey: string = 'children',
): Omit<T, typeof childrenKey>[] {
  const result: Omit<T, typeof childrenKey>[] = []

  function traverse(node: T, parentId: string | number | null = null) {
    // 创建新对象，不包含children属性
    const { [childrenKey]: _, ...rest } = node

    // 添加当前节点到结果数组
    result.push({
      ...rest,
      [parentIdKey]: parentId,
    } as Omit<T, typeof childrenKey>)

    // 如果有子节点，递归处理
    if (node[childrenKey] && Array.isArray(node[childrenKey])) {
      const currentId = node[idKey] as string | number
      const children = node[childrenKey] as T[]
      children.forEach((child) => traverse(child, currentId))
    }
  }

  tree.forEach((root) => traverse(root, null))

  return result
}

/**
 * 查找树节点
 * @param tree 树形结构数组
 * @param func 判断函数
 * @returns 找到的节点或null
 */
export function treeFind<T extends TreeNode>(tree: T[], func: (node: T) => boolean): T | null {
  for (const data of tree) {
    if (func(data)) {
      return data
    }
    if (data.children) {
      const res = treeFind(data.children as T[], func)
      if (res) {
        return res
      }
    }
  }
  return null
}

/**
 * 查找树节点路径
 * @param tree 树形结构数组
 * @param func 判断函数
 * @param path 当前路径（内部使用）
 * @returns 节点路径数组
 */
export function treeFindPath<T extends TreeNode>(
  tree: T[],
  func: (node: T) => boolean,
  path: T[] = [],
): T[] {
  if (!tree) {
    return []
  }
  for (const data of tree) {
    path.push(data)
    if (func(data)) {
      return path
    }
    if (data.children) {
      const findChildren = treeFindPath(data.children as T[], func, path)
      if (findChildren.length) {
        return findChildren
      }
    }
    path.pop()
  }
  return []
}
